202. 快乐数
202. 快乐数
分析
这一题 代码随想录 的解析并不好，他并没有说清楚为什么会出现无限循环。
我们在拿到题的时候，很快就能通过代码模拟输入一个数字之后判断其是不是快乐数的过程：拆分个十百千万位上的数字，然后求平方和，看等不等于 1，如果不等于就再递归调用一次这个过程，如果一个数字是快乐数，最终经过递归一定会得到 1，但是如果不是呢？这个循环会一直进行下去，最终抛出 StackOverflowError(因为我们是递归调用，而栈的最大深度是有限的)，所以这个题最难的地方其实是，如何判断一个数不是快乐数。
官方题解就说的很清楚：
输入任何一个数，不外乎以下三种可能。
- 最终会得到 1。
- 最终会进入循环。
- 值会越来越大，最后接近无穷大。
第三个情况比较难以检测和处理。我们怎么知道它会继续变大，而不是最终得到 1 呢？我们可以仔细想一想，每一位数的最大数字的下一位数是多少。
| Digits(位数) | Largest | Next |
|---|---|---|
| 1 | 9 | 81 |
| 2 | 99 | 162 |
| 3 | 999 | 243 |
| 4 | 9999 | 324 |
| 13 | 9999999999999 | 1053 |
| 对于 3 位数的数字，它不可能大于 243。这意味着它要么被困在 243 以下的循环内，要么跌到 1。 | ||
| 4 位或 4 位以上的数字在每一步都会丢失一位，直到降到 3 位为止。 | ||
| 所以我们知道，不管一开始输入的是什么数，最坏的情况下，算法可能会在 243 以下的所有数字上循环，然后回到它已经到过的一个循环或者回到 1。但它不会无限期地进行下去，所以我们排除第三种选择。 | ||
| 于是乎，思路也就出来了。 | ||
| 首先我们需要编写一个方法来获取下一个数，如果这个数字是 1，那就可以直接返回 true，如果不是，我们判断，这个数字是不是之前已经出现过了，如果是，说明进入了循环，直接返回 false，如果没有，我们则记录这个数字，然后进入下一个循环。 | ||
| 那我们用什么记录出现过的数字呢？因为我们不知道要保存的数字有多少个，没办法，只能使用高级的数据结构，就用 Set 吧。 |
解题
public boolean isHappy(int n) {
Set<Integer> records = new HashSet();
int now = n;
while(now!=1){
now = getNextNum(now);
if(records.contains(now)){
return false;
}else{
records.add(now);
}
}
return true;
}
public int getNextNum(int n){
int now = n;
int newInt = 0;
while(now!=0){
int left = now%10;
newInt+=left*left;
now = now/10;
}
return newInt;
}